package com.sam.book;

import java.util.LinkedList;
import java.util.List;

/**
 * 分离链接散列
 * Created by samwang on 2018/1/6.
 */
public class SeparateChainingHashTable<T> {
    public SeparateChainingHashTable() {
        this(DEFAULT_TABLE_SIZE);
    }

    public SeparateChainingHashTable(int size) {
        theLists = new List[nextPrime(size)];
        for (int i = 0; i < theLists.length; i++) {
            theLists[i] = new LinkedList<>();
        }
    }

    public void insert(T t) {
        List<T> whichList = theLists[myHash(t)];
        if (!whichList.contains(t)) {
            whichList.add(t);
            if (++currentSize > theLists.length) {
                rehash();
            }
        }
    }

    public void remove(T t) {
        List<T> whichList = theLists[myHash(t)];
        if (whichList.contains(t)) {
            whichList.remove(t);
            currentSize--;
        }
    }

    public boolean contains(T t) {
        List<T> whichList = theLists[myHash(t)];
        return whichList.contains(t);
    }

    public void makeEmpty() {
        for (List<T> theList : theLists) {
            theList.clear();
        }
        currentSize = 0;
    }

    private final static int DEFAULT_TABLE_SIZE = 101;

    private List<T>[] theLists;
    private int currentSize;

    private void rehash() {
        List<T>[] oldLists = theLists;
        theLists = new List[nextPrime(2 * theLists.length)];
        for (int i = 0; i < theLists.length; i++) {
            theLists[i] = new LinkedList<>();
        }

        for (int i = 0; i < oldLists.length; i++) {
            for (T t : oldLists[i]) {
                insert(t);
            }
        }

    }

    private int myHash(T t) {
        int hashVal = t.hashCode();
        hashVal %= theLists.length;
        if (hashVal < 0) {
            hashVal += theLists.length;
        }
        return hashVal;

    }

    private static int nextPrime(int n) {
        while (!isPrime(n + 1)) {
            n++;
        }
        return n;

    }

    private static boolean isPrime(int n){
        for (int i = 2; i <= Math.sqrt(n); i++) {

            if (i > 2 && i%2==0){
                continue;
            }

            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

}

/**
 * 测试类，使用String name来做equals和hashCode的计算
 */
class Employee {
    private String name;
    private double salary;
    private int seniority;

    @Override
    public boolean equals(Object rhs) {
        return rhs instanceof Employee && name.equals(((Employee) rhs).name);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}